Обсуждение:Решето Сундарама

Компактность реализации

Это утверждение требует как минимум пояснения:

От широко известного решета Эратосфена и более современного решета Аткина алгоритм отличается компактностью реализации на любом языке программирования.

Что значит пресловутая "компактость"? И почему, например, реализация решета Эратосфена некомпактна?

Вопрос

Здесь написано, что нужно исключать числа z=i+j+2ij, i=1,2,3..., j=1,2,3... Но если взять i=1, j=4, то z=1+4+2х1х4=13 - простое число! Так зачем его исключать? Dware 07:50, 6 декабря 2007 (UTC)

Потому что потом умножаются на 2 и прибавляется 1, а 13*2+1=25 - не простое! infovarius 09:29, 6 декабря 2007 (UTC)

Другой вариант реализации

В статье написано, что алгоритм Сундарама позволяет находить простые числа "до некоторого целого n". На самом деле этот алгоритм позволяет находить простые числа в любом заданном интервале натурального ряда, а не только с начала этого ряда. Приведу пример такой программы. Правда, программа написана на древнем Бейсике. Надо ввести в программу натуральное чётное число M>=4 и любое натуральное число L>M. Программа выдаст все простые числа в диапазоне от M+1 до L. В начале натурального ряда (при M = 4) программа не выдаёт первые два простых числа: 2 и 3.

5 PRINT "VVEDITE M"

7 INPUT M

8 IF INT(M / 2) <> M / 2 THEN 5

9 IF M < 4 THEN 5

10 PRINT "VVEDITE L"

11 INPUT L

12 FOR I = M + 1 TO L STEP 2

15 B = I: A = (B - 1) / 2

17 C = A - 1

20 FOR N = 1 TO C

25 K = (A - N) / (1 + 2 * N)

30 IF INT(K) = K THEN 40

35 NEXT N

36 W = W + 1: PRINT "#"; W

37 PRINT B

40 NEXT I

45 PRINT

50 END

На форуме dxdy.ru по моей просьбе любезно переписали представленную программу на языках Pascal и Turbo C++ 3.0. Ссылка:

http://dxdy.ru/post218607.html?sid=6723a4a0d1a58ddd42ca1a8eb19a8f9c#p218607

absolyut 07:42, 31 мая 2009 (UTC)